package ljl.alg.wangzheng_camp.round1.bfsdfs;

import java.util.*;

public class _17_22_word_convert {
    
    /**
     * 别人的解法，非常的慢 488ms
     */
    static class bfs {
        public List<String> findLadders(String beginWord, String endWord, List<String> wordList) {
            LinkedList<String> res = new LinkedList<>();
            int n = wordList.size();
            LinkedList<String> q = new LinkedList<>();
            boolean[] visited = new boolean[n];
            Map<String, String> prevMap = new HashMap<>();
            q.offer(beginWord);
            boolean found = false;
            while (!q.isEmpty()) {
                String cur = q.poll();
                if (cur.equals(endWord)) {
                    found = true;
                    break;
                }
                for (int i = 0; i < wordList.size(); i++) {
                    String each = wordList.get(i);
                    if (visited[i] || !offByOne(cur, each))
                        continue;
                    visited[i] = true;
                    q.offer(each);
                    prevMap.put(each, cur);
                }
            }
            if (!found)
                return res;
            String start = endWord;
            while (!prevMap.get(start).equals(beginWord)) {
                String prev = prevMap.get(start);
                res.addFirst(start);
                start = prev;
            }
            res.addFirst(start);
            res.addFirst(beginWord);
            
            return res;
        }
        
        boolean offByOne(String a, String b) {
            int len = a.length();
            int res = 0;
            for (int i = 0; i < len; i++) {
                if (a.charAt(i) != b.charAt(i))
                    res++;
                if (res == 2)
                    return false;
            }
            return true;
        }
    }
    
    static class dfs {
        LinkedList<String> path = new LinkedList<>();
        boolean[] visited;
        
        public List<String> findLadders(String beginWord, String endWord, List<String> wordList) {
            int n = wordList.size();
            visited = new boolean[n];
            path.add(beginWord);
            for (int i = 0; i < n; i++) {
                if (beginWord.equals(wordList.get(i))) {
                    visited[i] = true;
                }
            }
            if (dfs(beginWord, endWord, wordList)) return path;
            return new ArrayList<>();
        }
        
        boolean dfs(String from, String to, List<String> words) {
            if (from.equals(to)) return true;
            for (int i = 0; i < words.size(); i++) {
                String each = words.get(i);
                if (visited[i] || !offByOne(from, each)) continue;
                visited[i] = true;
                path.add(each);
                if (dfs(each, to, words)) return true;
                path.pollLast();
            }
            return false;
        }
        
        boolean offByOne(String a, String b) {
            int len = a.length();
            int res = 0;
            for (int i = 0; i < len; i++) {
                if (a.charAt(i) != b.charAt(i))
                    res++;
                if (res == 2)
                    return false;
            }
            return true;
        }
    }
    
    /**
     * 用 map 实现的 bfs
     * 居然还他妈的挺快，我是没想到的
     * */
    static class bfs2 {
    
        public List<String> findLadders(String beginWord, String endWord, List<String> wordList) {
            int n = beginWord.length();
            Map<String, List<String>> synonymMap = new HashMap<>();
            wordList.forEach(word -> {
                for (int i = 0; i < n; i++) {
                    synonymMap
                        .computeIfAbsent(word.substring(0, i) + '.' + word.substring(i + 1), k -> new ArrayList<>())
                        .add(word);
                }
            });
            Map<String, List<String>> pathMap = new HashMap<>();
            pathMap.put(beginWord, Collections.singletonList(beginWord));
            LinkedList<String> q = new LinkedList<>();
            q.offer(beginWord);
            while (!q.isEmpty()) {
//                String cur = q.poll();
                String cur = q.pop();
                if (cur.equals(endWord)) {
                    return pathMap.get(endWord);
                }
                for (int i = 0; i < n; i++) {
                    String each = cur.substring(0, i) + '.' + cur.substring(i + 1);
                    if (synonymMap.containsKey(each)) {
                        synonymMap.get(each).forEach(synonym -> {
                            if (!pathMap.containsKey(synonym)) {
                                List<String> path = new ArrayList<>(pathMap.get(cur));
                                path.add(synonym);
                                pathMap.put(synonym, path);
//                                q.offer(synonym);
                                q.push(synonym);
                            }
                        });
                    }
                }
            }
            return new ArrayList<>();
        }
    }
    
}
